package arrays;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**题目：求滑动窗口的最大值个数
 * @Author Gavin
 * @date 2022.01.23 16:27
 */
public class array_17 {
    /**
     *
     * 解题思路：
     * 暴力破解法
     */
    //Time:O(n*log(k)) Space:O(k)
    public static int[] solution(int[] nums,int k){
        if(nums==null || nums.length==0||k<=0)return nums;
        int n=nums.length;
        int[] result=new int[n-k+1];
        for (int left=0;left<=n-k;++left){
            int max=nums[left];
            for (int i = left; i < left + k; i++) {
                max=Math.max(max,nums[i]);
            }
            result[left]=max;
        }
        return result;
    }
    /**
     * 第二种方法，使用一个大顶堆
     */
    public ArrayList<Integer> solution_2(int[] num, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < k; i++) {
            queue.add(num[i]);
        }
        result.add(queue.peek());
        for (int i = 0, j = k + i; j < num.length; i++, j++) {
            queue.remove(num[i]);//这里是remove，不是poll,移除指定元素
            queue.add(num[j]);
            result.add(queue.peek());
        }
        return result;
    }

}
